<html>
<head><meta charset="utf-8"><title>recursive type with more than ~2^16 elements · general · Zulip Chat Archive</title></head>
<h2>Stream: <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/index.html">general</a></h2>
<h3>Topic: <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/recursive.20type.20with.20more.20than.20~2.5E16.20elements.html">recursive type with more than ~2^16 elements</a></h3>

<hr>

<base href="https://rust-lang.zulipchat.com">

<head><link href="https://rust-lang.github.io/zulip_archive/style.css" rel="stylesheet"></head>

<a name="234194803"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/recursive%20type%20with%20more%20than%20%7E2%5E16%20elements/near/234194803" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jake Vossen <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/recursive.20type.20with.20more.20than.20~2.5E16.20elements.html#234194803">(Apr 12 2021 at 17:04)</a>:</h4>
<p>So I totally expect the answer to be "nothing can be done", but I ran into an issue where I have a recursive type that is causing a stack overflow. Here is a minimal reproducible example:</p>
<div class="codehilite" data-code-language="Rust"><pre><span></span><code><span class="k">enum</span> <span class="nc">List</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">    </span><span class="n">Cons</span><span class="p">(</span><span class="kt">usize</span><span class="p">,</span><span class="w"> </span><span class="nb">Box</span><span class="o">&lt;</span><span class="n">List</span><span class="o">&gt;</span><span class="p">),</span><span class="w"></span>
<span class="w">    </span><span class="n">Nil</span><span class="p">,</span><span class="w"></span>
<span class="p">}</span><span class="w"></span>
<span class="k">fn</span> <span class="nf">main</span><span class="p">()</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">    </span><span class="kd">let</span><span class="w"> </span><span class="k">mut</span><span class="w"> </span><span class="n">list</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">List</span>::<span class="n">Nil</span><span class="p">;</span><span class="w"></span>

<span class="w">    </span><span class="k">for</span><span class="w"> </span><span class="n">n</span><span class="w"> </span><span class="k">in</span><span class="w"> </span><span class="mi">0</span><span class="o">..</span><span class="p">(</span><span class="mi">2_</span><span class="k">usize</span><span class="p">.</span><span class="n">pow</span><span class="p">(</span><span class="mi">17</span><span class="p">))</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">        </span><span class="n">list</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">List</span>::<span class="n">Cons</span><span class="p">(</span><span class="n">n</span><span class="p">,</span><span class="w"> </span><span class="nb">Box</span>::<span class="n">new</span><span class="p">(</span><span class="n">list</span><span class="p">));</span><span class="w"></span>
<span class="w">    </span><span class="p">}</span><span class="w"></span>
<span class="w">    </span><span class="fm">println!</span><span class="p">(</span><span class="s">"Finished loop"</span><span class="p">);</span><span class="w"></span>
<span class="w">    </span><span class="nb">drop</span><span class="p">(</span><span class="n">list</span><span class="p">);</span><span class="w"></span>
<span class="w">    </span><span class="fm">println!</span><span class="p">(</span><span class="s">"won't see me!"</span><span class="p">);</span><span class="w"></span>
<span class="p">}</span><span class="w"></span>
</code></pre></div>
<p>(It fails at some point between 2^16 and 2^17). I have an actual use case for this (representing a very tall AST in a parser for a really large file), what can be done?</p>



<a name="234195497"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/recursive%20type%20with%20more%20than%20%7E2%5E16%20elements/near/234195497" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Mario Carneiro <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/recursive.20type.20with.20more.20than.20~2.5E16.20elements.html#234195497">(Apr 12 2021 at 17:09)</a>:</h4>
<p>This is covered in the too many linked lists book</p>



<a name="234195522"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/recursive%20type%20with%20more%20than%20%7E2%5E16%20elements/near/234195522" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Mario Carneiro <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/recursive.20type.20with.20more.20than.20~2.5E16.20elements.html#234195522">(Apr 12 2021 at 17:09)</a>:</h4>
<p>you have to manually implement the destructor</p>



<a name="234195655"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/recursive%20type%20with%20more%20than%20%7E2%5E16%20elements/near/234195655" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Mario Carneiro <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/recursive.20type.20with.20more.20than.20~2.5E16.20elements.html#234195655">(Apr 12 2021 at 17:10)</a>:</h4>
<p><a href="https://rust-unofficial.github.io/too-many-lists/first-drop.html">https://rust-unofficial.github.io/too-many-lists/first-drop.html</a></p>



<a name="234196026"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/recursive%20type%20with%20more%20than%20%7E2%5E16%20elements/near/234196026" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jake Vossen <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/recursive.20type.20with.20more.20than.20~2.5E16.20elements.html#234196026">(Apr 12 2021 at 17:12)</a>:</h4>
<p>Ah, I see</p>



<a name="234196220"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/recursive%20type%20with%20more%20than%20%7E2%5E16%20elements/near/234196220" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jake Vossen <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/recursive.20type.20with.20more.20than.20~2.5E16.20elements.html#234196220">(Apr 12 2021 at 17:14)</a>:</h4>
<p>Except it isn't a plain old simple linked list but a more complicated graph...</p>



<a name="234196877"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/recursive%20type%20with%20more%20than%20%7E2%5E16%20elements/near/234196877" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Mario Carneiro <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/recursive.20type.20with.20more.20than.20~2.5E16.20elements.html#234196877">(Apr 12 2021 at 17:19)</a>:</h4>
<p>You still should either try to find a way to perform the destruction without a deep recursion, or else use something like <a href="https://docs.rs/stacker/0.1.13/stacker/"><code>stacker</code></a> to give yourself a huge stack for this problem</p>



<a name="234197464"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/recursive%20type%20with%20more%20than%20%7E2%5E16%20elements/near/234197464" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jake Vossen <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/recursive.20type.20with.20more.20than.20~2.5E16.20elements.html#234197464">(Apr 12 2021 at 17:23)</a>:</h4>
<p>I see. Thank you!</p>



<hr><p>Last updated: Aug 07 2021 at 22:04 UTC</p>
</html>